package com.hqq.exercise.list;

/**
 * LastNNodeInList 链表中倒数第k个结点
 * 题目描述:
 * 输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第一个结点
 * 输入样例:
 * {1,2,3,4,5,6},3
 * 输出样例:
 * 4
 * Created by heqianqian on 2017/8/10.
 */
public class LastNNodeInList {

    public static ListNode getLastNNode(ListNode root, int n) {
        int count = countNode(root);
        if (root == null || n < 0 || n > count) {
            throw new RuntimeException("参数不正确");
        }
        for (int i = 0; i < count - n; i++) {
            root = root.next;
        }
        return root;
    }

    /**
     * 计算链表节点数
     *
     * @param root 头节点
     * @return 节点个数
     */
    private static int countNode(ListNode root) {
        int count = 0;
        while (root != null) {
            count++;
            root = root.next;
        }
        return count;
    }
}
